ヾ(^▽^ヾ)
嗨，我是wec，今天是DAY 23。

🔎 題目難度與描述

難度：MEDIUM

題目描述：

一個由0和1組成的二維矩陣，0代表水，1代表陸地。矩陣中有兩個島嶼，島嶼由相鄰的1組成（上下左右相連）。你可以把0變成1，這樣就可以搭建橋來連接兩個島嶼。找出搭建最短橋的步數(把0變1)。

🔎 解題思路＆程式碼

1️⃣ 佇列

第1步： 用DFS找到第一個島嶼，並把它的所有1標記為2，方便區分，並將這些位置存入佇列。
第2步： 用BFS從佇列中的位置開始，不斷向四周擴展，尋找另一個島嶼。
第3步： 每次擴展到0時，繼續前進並記錄步數；當遇到1（第二個島嶼）時，表示找到了最短的橋，然後return步數。
程式碼：

def shortest_bridge(grid)
  n = grid.size
  queue = []

  directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
  
  def dfs(grid, x, y, queue)
    return if x < 0 || y < 0 || x >= grid.size || y >= grid[0].size || grid[x][y] != 1

    grid[x][y] = 2
    queue.push([x, y])
    directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    directions.each { |dx, dy| dfs(grid, x + dx, y + dy, queue) }
  end

  found = false
  (0...n).each do |i|
    break if found
    (0...n).each do |j|
      if grid[i][j] == 1
        dfs(grid, i, j, queue)
        found = true
        break
      end
    end
  end

  steps = 0
  while !queue.empty?
    size = queue.size
    size.times do
      x, y = queue.shift

      directions.each do |dx, dy|
        nx, ny = x + dx, y + dy

        if nx >= 0 && ny >= 0 && nx < n && ny < n
          if grid[nx][ny] == 1 
            return steps
          end
          if grid[nx][ny] == 0
            grid[nx][ny] = 2
            queue.push([nx, ny])
          end
        end
      end
    end
    steps += 1
  end

  steps
end

🔎 總結

時間複雜度

佇列： O(n²)，n為矩陣邊長。
➡️ 這題最有挑戰性的地方在於需要同時用到DFS和BFS，兩種方法一起用對於這種網格或是要找路徑的題目非常有幫助，雖然步驟有點繁瑣，不過還好ruby是蠻好閱讀的語言，所以不難理解d(-∀-●)!!

那麽，以上就是今天的內容！

相信IT人動腦時都要吃點東西，所以今天邊寫邊吃草莓口味的仙貝。
明天要說：Ruby精選刷題！Medium路跑D-16(>∀･)⌒☆